package toOffer;

/**
 * @author YuanAo
 * @date 2024/7/8 14:26
 * @description LCR39-直方图最大矩形面积
 */

import java.util.Stack;

/**
 * 题目：直方图是由排列在同一基线上的相邻柱子组成的图形。输入一
 * 个由非负数组成的数组，数组中的数字是直方图中柱子的高。求直方图中
 * 最大矩形面积。假设直方图中柱子的宽都为1。例如，输入数组[3, 2, 5, 4, 6,
 * 1, 4, 2]，其对应的直方图如图6.3所示，该直方图中最大矩形面积为12，如
 * 阴影部分所示。
 */
public class toOffer6_2_39 {
    public static void main(String[] args) {
        int[] heights = {2, 1, 5, 6, 2, 3};
        System.out.println(largestRectangleArea(heights));
    }

    /**
     * 单调栈
     *
     * @param heights
     * @return
     */
    public static int largestRectangleArea2(int[] heights) {
        int mathArea = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < heights.length; i++) {
            if (stack.isEmpty() || heights[stack.peek()] < heights[i]) {
                stack.push(i);
            } else if (heights[stack.peek()] > heights[i]) {
                mathArea = Math.max(mathArea, (i - stack.peek() + 1) * heights[i]);
            }
        }

        return mathArea;
    }

    public static int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        // -1充当栈底
        stack.push(-1);
        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            // 栈不为空且栈顶元素值大于等于当前数组元素值
            while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
                int height = heights[stack.pop()];
                int width = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }

        while (stack.peek() != -1) {
            int height = heights[stack.pop()];
            int width = heights.length - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        return maxArea;
    }

    /**
     * 暴力
     *
     * @param heights
     * @return
     */
    public static int largestRectangleArea1(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int tempNum;
        int min;
        for (int i = 0; i < heights.length; i++) {
            min = heights[i];
            for (int j = i; j < heights.length; j++) {
                min = Math.min(min, heights[j]);
                tempNum = (j - i + 1) * min;
                if (stack.isEmpty() || stack.peek() < tempNum) {
                    stack.push(tempNum);
                }
            }
        }

        return stack.peek();
    }
}